package DataStructures.Stack;

import com.sun.org.apache.xerces.internal.impl.xpath.XPath;
import org.omg.CORBA.PUBLIC_MEMBER;

import javax.management.StringValueExp;
import javax.swing.plaf.synth.SynthTextAreaUI;
import java.util.ArrayList;
import java.util.Collection;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.Stack;

/**
 * @author ：ALi
 * @date ：Created in 2021/11/6 13:57
 * @description：中缀表达式转后缀表达式
 * @modified By：
 * @version: $
 */
public class suffixExpression {

    public static void main(String[] args){
        String str = "1.0+((2+3)*4)-5";
        //得到中缀表达式的list形式
        List<String> list = toInFixExpressionList(str);
        System.out.println(list);

        List<String> SuffixList = pareseSuffixExpreesionList(list);
        System.out.println(SuffixList);

    }
    /**
     * create by: ALi
     * description: 将字符串"1+((2+3)*4)-5"变为list:[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5]
     * create time: 2021/11/6 14:01
     * @Param: string:"1+((2+3)*4)-5"
     * @return [1, +, (, (, 2, +, 3, ), *, 4, ), -, 5]
     */
    public static List<String> toInFixExpressionList(String string){
        List<String> list = new ArrayList<String>();
        char c;
        String str ="";//拼接数字
        for (int i = 0;i<string.length();){
            c = string.charAt(i);

            if(c < 48 || c > 57){//c非数字
                list.add("" + c);
                i++;
            }else {
                str = "";
                //拼接数字
                while (i<string.length() && (c=string.charAt(i)) >= 48 && (c=string.charAt(i)) <= 57){
                    str = str + c;
                    i++;
                }
                list.add(str);
            }

        }
    return list;
    }


    /**
     * create by: ALi
     * description: 由中缀表达式=>后缀表达式
     * create time: 2021/11/6 14:30
     *
      * @Param: list:[1, +, (, (, 2, +, 3, ), *, 4, ), -, 5]
     * @return [1, 2, 3, +, 4, *, +, 5, -]
     */
    public static List<String> pareseSuffixExpreesionList(List<String> list){

        Stack<String> signStack = new Stack<String>();//符号栈
        List<String> numberList = new ArrayList<>();//数字list

        //遍历list
        for (String item:list){
            //是数字的情况
            if (item.matches("\\d+")){
                numberList.add(item);
            }
            //不是数字的情况
            else {
                //为左括号或者字符栈为空，直接进栈
                if(item.equals("(") || signStack.empty()){
                    signStack.push(item);
                }else{
                    //为右括号的时候
                    if(item.equals(")")){
                        //与栈顶符号比较，如果是不是左括号就进数字list直到遇到“（”为止，然后将（弹出栈
                        while (true){
                            if(signStack.peek().equals("(")){
                                break;
                            }
                            numberList.add(signStack.pop());
                        }
                        //将“（”弹出
                        signStack.pop();
                    }else {//非括号的运算符
                        //item的优先级小于signStack顶的元素
                        while (signStack.size() != 0 && Operation(item) <= Operation(signStack.peek())){
                            numberList.add(signStack.pop());
                        }
                        //将item压入栈中
                        signStack.push(item);

                    }
                }
            }
        }
        while (signStack.size() != 0){
            numberList.add(signStack.pop());
        }




        return numberList;//存入list是有序的，正常输出就是后缀表达式
    }
    /**
     * create by: ALi
     * description: 判断优先级
     * create time: 2021/11/6 15:10
     *
      * @Param: null
     * @return
     */

    public static int Operation(String str){
        int sum = 0;
        if(str.equals("+")){
            sum = 1;
        }
        if(str.equals("-")){
            sum = 1;
        }
        if(str.equals("*")){
            sum = 3;
        }
        if(str.equals("/")){
            sum = 3;
        }
        return sum;
    }

}